/**
 * Copyright (c) 2007-2008 Nearchos Paspallis
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * AspectSense
 *
 * Middleware for annotation-based, context-aware and adaptive services for
 * mobile and ubiquitous computing
 *
 * This project is an open-source effort, initiated by Nearchos Paspallis as
 * part of his PhD work at the University of Cyprus (http://www.ucy.ac.cy).
 *
 * More information about the project is available at "http://aspectsense.org".
 */

package org.aspectsense.graphs;

import java.util.*;

/**
 * Todo convert to immutable implementation
 *
 * @author Nearchos Paspallis [nearchos@cs.ucy.ac.cy]
 *         Date: Dec 21, 2007
 *         Time: 8:58:42 AM
 */
public class DefaultDirectedBipartiteGraph<E> implements DirectedBipartiteGraph<E>
{
    private final Set<Node<E>> leftPartitionNodes = new HashSet<Node<E>>();

    private final Set<Node<E>> rightPartitionNodes = new HashSet<Node<E>>();

    private final Set<DirectedEdge<E>> directedEdges = new HashSet<DirectedEdge<E>>();

    public DefaultDirectedBipartiteGraph()
    {
        super();
    }

    public void addAllEdges(final Set<DirectedEdge<E>> directedEdges)
    {
        while (!directedEdges.isEmpty())
        {
            boolean edgeAdded = false;

            final Iterator<DirectedEdge<E>> iterator = directedEdges.iterator();
            DirectedEdge<E> directedEdge = null;
            while (iterator.hasNext())
            {
                directedEdge = iterator.next();

                // check if the specified directed edge has a node in either group
                final Node<E> fromNode = directedEdge.getFromNode();
                final Node<E> toNode = directedEdge.getToNode();
                if(leftPartitionNodes.contains(fromNode) || rightPartitionNodes.contains(toNode))
                {
                    addEdge(directedEdge, fromNode, toNode);
                    edgeAdded = true;
                    iterator.remove();
                }
                else if(leftPartitionNodes.contains(toNode) || rightPartitionNodes.contains(fromNode))
                {
                    addEdge(directedEdge, toNode, fromNode);
                    edgeAdded = true;
                    iterator.remove();
                }
            }

            if(!edgeAdded)
            {
                assert directedEdge != null;
                addEdge(directedEdge, directedEdge.getFromNode(), directedEdge.getToNode());
                directedEdges.remove(directedEdge);
            }
        }
    }

    public void addEdge(final DirectedEdge<E> directedEdge,
                        final Node<E> leftPartitionNode,
                        final Node<E> rightPartitionNode)
    {
        if(rightPartitionNodes.contains(leftPartitionNode))
        {
            throw new IllegalArgumentException("The specified edge's " +
                    "left-partition-node is already included in the right " +
                    "partition.");
        }

        if(leftPartitionNodes.contains(rightPartitionNode))
        {
            throw new IllegalArgumentException("The specified edge's " +
                    "right-partition-node is already included in the left " +
                    "partition.");
        }

        directedEdges.add(directedEdge);
        leftPartitionNodes.add(leftPartitionNode);
        rightPartitionNodes.add(rightPartitionNode);
    }

    public void removeAllEdges(final Set<DirectedEdge<E>> directedEdges)
    {
        for(final DirectedEdge<E> directedEdge : directedEdges)
        {
            removeEdge(directedEdge);
        }
    }

    public void removeEdge(final DirectedEdge<E> directedEdge)
    {
        if(directedEdge == null)
        {
            throw new NullPointerException("Invalid null argument");
        }

        if(!directedEdges.contains(directedEdge))
        {
            throw new IllegalArgumentException("The edge to be removed is not contained in the graph: " + directedEdge);
        }

        final Node<E> fromNode = directedEdge.getFromNode();
        final Node<E> toNode = directedEdge.getToNode();

        assert leftPartitionNodes.contains(fromNode) ^ rightPartitionNodes.contains(fromNode);
        assert leftPartitionNodes.contains(toNode) ^ rightPartitionNodes.contains(toNode);
        assert (leftPartitionNodes.contains(fromNode) && rightPartitionNodes.contains(toNode))
                ^ (leftPartitionNodes.contains(toNode) && rightPartitionNodes.contains(fromNode));

        if(leftPartitionNodes.contains(fromNode))
        {
            leftPartitionNodes.remove(fromNode);
            rightPartitionNodes.remove(toNode);
        }
        else
        {
            leftPartitionNodes.remove(toNode);
            rightPartitionNodes.remove(fromNode);
        }
        directedEdges.remove(directedEdge);
    }

    public long getNumberOfNodes()
    {
        return leftPartitionNodes.size() + rightPartitionNodes.size();
    }

    public long getNumberOfEdges()
    {
        return directedEdges.size();
    }

    public Set<Node<E>> getNodes()
    {
        final Set<Node<E>> nodeSet = new HashSet<Node<E>>();
        nodeSet.addAll(leftPartitionNodes);
        nodeSet.addAll(rightPartitionNodes);

        return new HashSet<Node<E>>(nodeSet);
    }

    public Set<DirectedEdge<E>> getDirectedEdges()
    {
        return new HashSet<DirectedEdge<E>>(directedEdges);
    }

    public boolean containsLeftNode(final Node<E> node)
    {
        return leftPartitionNodes.contains(node);
    }

    public boolean containsRightNode(final Node<E> node)
    {
        return rightPartitionNodes.contains(node);
    }

    public boolean containsNode(final Node<E> node)
    {
        return containsLeftNode(node) || containsRightNode(node);
    }

    public boolean containsEdge(final DirectedEdge<E> directedEdge)
    {
        return directedEdges.contains(directedEdge);
    }

    public Set<Node<E>> getLeftPartition()
    {
        return new HashSet<Node<E>>(leftPartitionNodes);
    }

    public Set<Node<E>> getRightPartition()
    {
        return new HashSet<Node<E>>(rightPartitionNodes);
    }

    public BipartiteGraphDelta<E> computeDelta(final DefaultDirectedBipartiteGraph<E> target)
    {
        final DefaultDirectedBipartiteGraph<E> source = this;

        final Set<Node<E>> sameLeftNodes = new HashSet<Node<E>>();
        final Set<Node<E>> sameRightNodes = new HashSet<Node<E>>();
        final Set<Node<E>> addedLeftNodes = new HashSet<Node<E>>();
        final Set<Node<E>> addedRightNodes = new HashSet<Node<E>>();
        final Set<Node<E>> removedLeftNodes = new HashSet<Node<E>>();
        final Set<Node<E>> removedRightNodes = new HashSet<Node<E>>();

        final Set<Node<E>> sourceLeftNodes = source.getLeftPartition();
        final Set<Node<E>> sourceRightNodes = source.getRightPartition();
        final Set<Node<E>> targetLeftNodes = target.getLeftPartition();
        final Set<Node<E>> targetRightNodes = target.getRightPartition();

        for(final Node<E> node : sourceLeftNodes)
        {
            if(target.containsNode(node))
            {
                sameLeftNodes.add(node);
            }
            else
            {
                removedLeftNodes.add(node);
            }
        }

        for(final Node<E> node : sourceRightNodes)
        {
            if(target.containsNode(node))
            {
                sameRightNodes.add(node);
            }
            else
            {
                removedRightNodes.add(node);
            }
        }

        for(final Node<E> node : targetLeftNodes)
        {
            if(!sourceLeftNodes.contains(node))
            {
                addedLeftNodes.add(node);
            }
        }

        for(final Node<E> node : targetRightNodes)
        {
            if(!sourceRightNodes.contains(node))
            {
                addedRightNodes.add(node);
            }
        }

        final Set<DirectedEdge<E>> sameEdges = new HashSet<DirectedEdge<E>>();
        final Set<DirectedEdge<E>> addedEdges = new HashSet<DirectedEdge<E>>();
        final Set<DirectedEdge<E>> removedEdges = new HashSet<DirectedEdge<E>>();

        final Set<DirectedEdge<E>> sourceDirectedEdges = source.getDirectedEdges();
        final Set<DirectedEdge<E>> targetDirectedEdges = target.getDirectedEdges();

        for(final DirectedEdge<E> directedEdge : sourceDirectedEdges)
        {
            if(target.containsEdge(directedEdge))
            {
                sameEdges.add(directedEdge);
            }
            else
            {
                removedEdges.add(directedEdge);
            }
        }

        for(final DirectedEdge<E> directedEdge : targetDirectedEdges)
        {
            if(!sourceDirectedEdges.contains(directedEdge))
            {
                addedEdges.add(directedEdge);
            }
        }

        return new BipartiteGraphDelta<E>(
                sameLeftNodes, sameRightNodes, addedLeftNodes,
                addedRightNodes, removedLeftNodes, removedRightNodes,
                sameEdges, addedEdges, removedEdges);
    }

    public DefaultDirectedBipartiteGraph<E> computeMinGraphIncludingRightNodes(final Set<Node<E>> rightNodes)
    {
        if(rightNodes == null)
        {
            throw new NullPointerException("Illegal null argument!");
        }

        if(rightNodes.isEmpty())
        {
            return new DefaultDirectedBipartiteGraph<E>();
        }

        // check that all the given nodes are in the right partition
        for(final Node<E> node : rightNodes)
        {
            if(!rightPartitionNodes.contains(node))
            {
                throw new IllegalArgumentException("The specified node is not part of the right partition: " + node);
            }
        }

        // initiate the resulting bipartite, directed graph
        final DefaultDirectedBipartiteGraph<E> result = new DefaultDirectedBipartiteGraph<E>();

        // initialize the unprocessed-nodes queue with the input
        final Queue<Node<E>> unprocessedNodes = new LinkedList<Node<E>>(rightNodes);

        while(!unprocessedNodes.isEmpty())
        {
            final Node<E> node = unprocessedNodes.poll();
            final Set<DirectedEdge<E>> directedEdges = getDirectedEdgesTo(node);
            for(final DirectedEdge<E> directedEdge : directedEdges)
            {
                final Node<E> fromNode = directedEdge.getFromNode();
                final Node<E> toNode = directedEdge.getToNode();

                unprocessedNodes.add(fromNode);

                if(rightPartitionNodes.contains(toNode))
                {
                    result.addEdge(directedEdge, fromNode, toNode);
                }
                else
                {
                    // assert rightPartitionNodes.contains(toNode);
                    result.addEdge(directedEdge, toNode, fromNode);
                }
            }
        }

        return result;
    }

    public Set<DirectedEdge<E>> getDirectedEdgesFrom(final Node<E> fromNode)
    {
        final Set<DirectedEdge<E>> allEdgesFrom = new HashSet<DirectedEdge<E>>();

        for(final DirectedEdge<E> directedEdge : directedEdges)
        {
            if(directedEdge.getFromNode().equals(fromNode))
            {
                allEdgesFrom.add(directedEdge);
            }
        }

        return allEdgesFrom;
    }

    public Set<DirectedEdge<E>> getDirectedEdgesTo(final Node<E> toNode)
    {
        final Set<DirectedEdge<E>> allEdgesTo = new HashSet<DirectedEdge<E>>();

        for(final DirectedEdge<E> directedEdge : directedEdges)
        {
            if(directedEdge.getToNode().equals(toNode))
            {
                allEdgesTo.add(directedEdge);
            }
        }

        return allEdgesTo;
    }

    public boolean isEmpty()
    {
        return directedEdges.isEmpty();
    }

    public boolean existsPath(final Node<E> from, final Node<E> to)
    {
        Set<Node<E>> reachableNodes = new HashSet<Node<E>>();

        reachableNodes.add(from);

        while(!reachableNodes.isEmpty())
        {
            if(reachableNodes.contains(to)) return true;

            final Set<Node<E>> newReachableNodes = new HashSet<Node<E>>();
            for(final Node<E> node : reachableNodes)
            {
                final Set<DirectedEdge<E>> directedEdgesFromNode = getDirectedEdgesFrom(node);
                for(final DirectedEdge<E> directedEdge : directedEdgesFromNode)
                {
                    newReachableNodes.add(directedEdge.getToNode());
                }
            }

            reachableNodes = newReachableNodes;
        }

        return false;
    }

    public boolean equals(Object object)
    {
        if(object == null) return false;

        if(this == object) return true;

        if(object.getClass() != this.getClass())
        {
            return false;
        }

        final DefaultDirectedBipartiteGraph graph = (DefaultDirectedBipartiteGraph) object;

        return directedEdges.equals(graph.directedEdges)
                && leftPartitionNodes.equals(graph.leftPartitionNodes)
                && rightPartitionNodes.equals(graph.rightPartitionNodes);
    }

    private static String lastPart(final Object object)
    {
        final String string = object.toString();

        int index = string.lastIndexOf('.');
        if(index == -1)
        {
            return string;
        }
        else
        {
            return string.substring(index + 1);
        }
    }

    public String toShortString()
    {
        final StringBuilder stringBuilder = new StringBuilder();

        stringBuilder.append("DirectedBipartiteGraph:\n Nodes {(");

        final int leftPartitionSize = leftPartitionNodes.size();
        int lCount = 0;
        for(final Node node : leftPartitionNodes)
        {
            lCount++;
            stringBuilder.append(lastPart(node));
            if(lCount < leftPartitionSize) stringBuilder.append(", ");
        }
        final int rightPartitionSize = rightPartitionNodes.size();
        int rCount = 0;

        stringBuilder.append("), (");

        for(final Node node : rightPartitionNodes)
        {
            rCount++;
            stringBuilder.append(lastPart(node));
            if(rCount < rightPartitionSize) stringBuilder.append(", ");
        }

        stringBuilder.append(")},\nEdges {");

        for(final DirectedEdge<E> directedEdge : directedEdges)
        {
            final E lValue = directedEdge.getFromNode().getValue();
            final E rValue = directedEdge.getToNode().getValue();
            stringBuilder.append("\n(").append(lastPart(lValue)).append(" -> ").append(lastPart(rValue)).append(")");
        }

        stringBuilder.append("}");

        return stringBuilder.toString();
    }

    public String toString()
    {
        final StringBuilder stringBuilder = new StringBuilder();

        stringBuilder.append("DirectedBipartiteGraph:\n Nodes {(");

        final int leftPartitionSize = leftPartitionNodes.size();
        int lCount = 0;
        for(final Node node : leftPartitionNodes)
        {
            lCount++;
            stringBuilder.append(node.getValue());
            if(lCount < leftPartitionSize) stringBuilder.append(", ");
        }
        final int rightPartitionSize = rightPartitionNodes.size();
        int rCount = 0;

        stringBuilder.append("), (");

        for(final Node node : rightPartitionNodes)
        {
            rCount++;
            stringBuilder.append(node.getValue());
            if(rCount < rightPartitionSize) stringBuilder.append(", ");
        }

        stringBuilder.append(")},\nEdges {");

        for(final DirectedEdge<E> directedEdge : directedEdges)
        {
            final E lValue = directedEdge.getFromNode().getValue();
            final E rValue = directedEdge.getToNode().getValue();
            stringBuilder.append("\n(").append(lValue).append("->").append(rValue).append(")");
        }

        stringBuilder.append("}");

        return stringBuilder.toString();
    }
}